{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Mountain in Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #dynamic-programming #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #动态规划 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestMountain"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组中的最长山脉"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>把符合下列属性的数组 <code>arr</code> 称为 <strong>山脉数组</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>arr.length &gt;= 3</code></li>\n",
    "\t<li>存在下标 <code>i</code>（<code>0 &lt; i &lt; arr.length - 1</code>），满足\n",
    "\t<ul>\n",
    "\t\t<li><code>arr[0] &lt; arr[1] &lt; ... &lt; arr[i - 1] &lt; arr[i]</code></li>\n",
    "\t\t<li><code>arr[i] &gt; arr[i + 1] &gt; ... &gt; arr[arr.length - 1]</code></li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>给出一个整数数组 <code>arr</code>，返回最长山脉子数组的长度。如果不存在山脉子数组，返回 <code>0</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [2,1,4,7,3,2,5]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>最长的山脉子数组是 [1,4,7,3,2]，长度为 5。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [2,2,2]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>不存在山脉子数组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= arr[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>你可以仅用一趟扫描解决此问题吗？</li>\n",
    "\t<li>你可以用 <code>O(1)</code> 空间解决此问题吗？</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-mountain-in-array](https://leetcode.cn/problems/longest-mountain-in-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-mountain-in-array](https://leetcode.cn/problems/longest-mountain-in-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,4,7,3,2,5]', '[2,2,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ans = left = 0\n",
    "        right = 0\n",
    "        while left + 2 < n: #长度至少3\n",
    "            right = left + 1\n",
    "            if arr[left] < arr[right]:\n",
    "                while right + 1 < n and arr[right] < arr[right + 1]:\n",
    "                    right += 1\n",
    "                if right < n - 1 and arr[right] > arr[right + 1]:\n",
    "                    while right + 1 < n and arr[right] > arr[right + 1]:\n",
    "                        right += 1\n",
    "                    ans = max(ans, right - left + 1)\n",
    "                else:\n",
    "                    right += 1\n",
    "            left = right\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        longest_len = 0\n",
    "\n",
    "        for i in range(1,n-1):\n",
    "            #寻找山顶\n",
    "            if arr[i-1] < arr[i] and arr[i] > arr[i+1]:\n",
    "                left_len = right_len = 0\n",
    "                # 向左统计递减序列的长度\n",
    "                j = i\n",
    "                while j > 0 and arr[j-1] < arr[j]:\n",
    "                    j -= 1\n",
    "                    left_len += 1\n",
    "                # 向右统计递减序列的长度\n",
    "                k = i\n",
    "                while k < n-1 and arr[k] > arr[k+1]:\n",
    "                    k += 1\n",
    "                    right_len += 1\n",
    "                # 更新最长山脉子数组的长度\n",
    "                longest_len = max(longest_len,left_len+right_len+1)\n",
    "        return longest_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[1]*2 for _ in range(n)]\n",
    "        ret = 0\n",
    "        for i in range(1,n):\n",
    "            if arr[i]-arr[i-1]>0:\n",
    "                dp[i][1] = dp[i-1][1]+1\n",
    "        \n",
    "        for i in range(n-1)[::-1]:\n",
    "            if arr[i]-arr[i+1]>0:\n",
    "                dp[i][0] = dp[i+1][0]+1\n",
    "        \n",
    "        for d in dp:\n",
    "            if d[0] > 1 and d[1] > 1:\n",
    "                ret = max(ret,d[0]+d[1]-1)\n",
    "\n",
    "        return ret if ret > 2 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        for i in range(1, n - 1):\n",
    "            if arr[i - 1] < arr[i] and arr[i] > arr[i + 1]:\n",
    "                left = right = i\n",
    "                while left > 0 and arr[left - 1] < arr[left]:\n",
    "                    left -= 1\n",
    "                while right < n - 1 and arr[right + 1] < arr[right]:\n",
    "                    right += 1\n",
    "                ans = max(ans, right - left + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        zhuangTaiSave = [0,arr[0]]\n",
    "        arr[0] = 1\n",
    "        size = len(arr)\n",
    "        for i in range(1,size):\n",
    "            if zhuangTaiSave[0] == 1:\n",
    "                if arr[i]>zhuangTaiSave[1]:\n",
    "                    zhuangTaiSave[0] = 1\n",
    "                    zhuangTaiSave[1] = arr[i]\n",
    "                    arr[i] = arr[i-1] + 1\n",
    "                elif arr[i]<zhuangTaiSave[1]:\n",
    "                    zhuangTaiSave[0] = -1\n",
    "                    zhuangTaiSave[1] = arr[i]\n",
    "                    arr[i] = arr[i-1] + 1\n",
    "                elif arr[i] == zhuangTaiSave[1]:\n",
    "                    zhuangTaiSave[0] = 0\n",
    "                    zhuangTaiSave[1] = arr[i]\n",
    "                    arr[i] = 1\n",
    "                    for j in range(i-arr[i-1] + 1,i):\n",
    "                        arr[j] = 0\n",
    "            elif zhuangTaiSave[0] == 0:\n",
    "                if arr[i]>zhuangTaiSave[1]:\n",
    "                    zhuangTaiSave[0] = 1\n",
    "                    zhuangTaiSave[1] = arr[i]\n",
    "                    arr[i] = arr[i-1] + 1\n",
    "                else:\n",
    "                    zhuangTaiSave[0] = 0\n",
    "                    zhuangTaiSave[1] = arr[i]\n",
    "                    arr[i] = 1\n",
    "            elif zhuangTaiSave[0] == -1:\n",
    "                if arr[i]>zhuangTaiSave[1]:\n",
    "                    zhuangTaiSave[0] = 1\n",
    "                    zhuangTaiSave[1] = arr[i]\n",
    "                    arr[i] = 2\n",
    "                elif arr[i]<zhuangTaiSave[1]:\n",
    "                    zhuangTaiSave[0] = -1\n",
    "                    zhuangTaiSave[1] = arr[i]\n",
    "                    arr[i] = arr[i-1] + 1\n",
    "                elif arr[i] == zhuangTaiSave[1]:\n",
    "                    zhuangTaiSave[0] = 0\n",
    "                    zhuangTaiSave[1] = arr[i]\n",
    "                    arr[i] = 0\n",
    "        \n",
    "        \n",
    "        if zhuangTaiSave[0] == 1:\n",
    "            for i in range(size - arr[size-1] + 1,size):\n",
    "                arr[i] = 0\n",
    "        res = max(arr)\n",
    "        if res < 3:\n",
    "            return 0\n",
    "        else:\n",
    "            return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        # 1 找left点\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        while left < n:\n",
    "            while left < n -1 and arr[left+1] <= arr[left]:\n",
    "                left += 1\n",
    "            # 2 从left开始找peak点\n",
    "            peak= left + 1\n",
    "            while peak < n - 1 and arr[peak+1] > arr[peak]:\n",
    "                peak += 1\n",
    "            # 3 从peak点找right点\n",
    "            right= peak\n",
    "            while right < n - 1 and arr[right+1] <  arr[right]:\n",
    "                right += 1\n",
    "                ans = max(ans, right - left + 1)\n",
    "            left = right\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #首先遍历 arr，寻找所有可能的山峰点。只有右侧的点小于当前点，即 arr[i + 1] < arr[i] ，才有可能是山峰。当找到山峰点，我们定义 l 和 r 分别向左向右寻找山脚，记入ans。主要是寻找山峰点。\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        k=len(arr)\n",
    "        max_len=0\n",
    "        if(k<3):\n",
    "            return 0\n",
    "        for i in range(1,k-1):\n",
    "            l,r=i,i\n",
    "            #计算到中间值最高的\n",
    "            if(arr[i]>arr[i-1]) and (arr[i]>arr[i+1]):\n",
    "                while l-1>=0 and arr[l]>arr[l-1]:\n",
    "                    l-=1\n",
    "                while r+1<k and arr[r]>arr[r+1]:\n",
    "                    r+=1\n",
    "                max_len = max(max_len,r-l+1)\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        cnt = 1\n",
    "        ans = 0\n",
    "        down = False\n",
    "        for x, y in pairwise(arr):\n",
    "            if x < y:\n",
    "                if down:\n",
    "                    down = False\n",
    "                    cnt = 1\n",
    "                cnt += 1\n",
    "            elif down := x > y:\n",
    "                if cnt > 1:\n",
    "                    cnt += 1\n",
    "                    if cnt > ans:\n",
    "                        ans = cnt\n",
    "            else:\n",
    "                cnt = 1\n",
    "\n",
    "        return ans  \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        if len(arr) < 3:\n",
    "            return 0\n",
    "        pending_flag = -1\n",
    "        idx_gap = 1\n",
    "        index = 0\n",
    "        longest = 0\n",
    "        gaps = []\n",
    "        for index in range(len(arr)):\n",
    "            if index == 0:\n",
    "                continue\n",
    "            print(f\"{arr[index - 1]} | {arr[index]}\")\n",
    "            if arr[index - 1] < arr[index]:\n",
    "                if pending_flag == -1:\n",
    "                    pending_flag = 1\n",
    "                elif pending_flag == 0: # negative\n",
    "                    print(f\"GAP at {index}\")\n",
    "                    gaps.append((index - idx_gap, pending_flag))\n",
    "                    longest = max(longest, index - idx_gap)\n",
    "                    idx_gap = index\n",
    "                    pending_flag = 1\n",
    "                elif pending_flag == 1:\n",
    "                    continue\n",
    "            elif arr[index - 1] > arr[index]:\n",
    "                if pending_flag == -1:\n",
    "                    pending_flag = 0\n",
    "                elif pending_flag == 1: # positive\n",
    "                    print(f\"GAP at {index}\")\n",
    "                    gaps.append((index - idx_gap, pending_flag))\n",
    "                    longest = max(longest, index - idx_gap)\n",
    "                    idx_gap = index\n",
    "                    pending_flag = 0\n",
    "                elif pending_flag == 0:\n",
    "                    continue\n",
    "            elif arr[index - 1] == arr[index]:\n",
    "                pending_flag = -1\n",
    "                print(f\"GAP at {index}\")\n",
    "                gaps.append((index - idx_gap, pending_flag))\n",
    "                longest = max(longest, index - idx_gap)\n",
    "                idx_gap = index + 1\n",
    "        # if index - idx_gap != 0:\n",
    "        index += 1\n",
    "        gaps.append((index - idx_gap, pending_flag))\n",
    "        print(gaps)\n",
    "        longest = 0\n",
    "        for index in range(1, len(gaps)):\n",
    "            if gaps[index][1] == 0 and gaps[index-1][1] == 1 or gaps[index][1] == -1 and gaps[index-1][1] == 1:\n",
    "                longest = max(longest, gaps[index][0] + 1 + gaps[index-1][0])\n",
    "        return longest if longest >= 3 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        # 遇到上升记录左侧\n",
    "        l, ans, up, down = 0, 0, False, False\n",
    "        for i in range(1, len(arr)):\n",
    "            # 升\n",
    "            if arr[i] > arr[i-1]:\n",
    "                if down: # 前面是降重新定位升的开始位置\n",
    "                    l = i - 1\n",
    "                up = True\n",
    "                down = False\n",
    "            # 降\n",
    "            elif arr[i] < arr[i-1]:\n",
    "                down = True\n",
    "            else: # 相等的\n",
    "                l = i\n",
    "                down = False\n",
    "                up = False\n",
    "                continue\n",
    "            # 先升后降\n",
    "            if up and down:\n",
    "                ans = max(ans, i - l + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        双指针枚举 从左到右遍历数组 一个指针枚举左侧山脚 另外一个不断右移移动到右侧山脚\n",
    "        左侧山脚left 一定满足arr[left]<arr[left+1]\n",
    "        右侧山脚初始为left+1 随后不断右移right 直到不满足arr[right]<arr[right+1] 这时\n",
    "            如果right=n-1说明无法形成山脉\n",
    "            否则他就可能是山顶 需要额外判断arr[right]>arr[right]+1\n",
    "        一旦right找到山顶 就采用类似方法右移right 直到找到右侧山脚\n",
    "        一旦找到一个山脉 下一次探测left即是right\n",
    "        但是其余情况right都是 因此更新为right+1\n",
    "        \"\"\"\n",
    "        n = len(arr)\n",
    "        rs = left = 0\n",
    "        while left+2<n: #山脉最小长度为3\n",
    "            right = left+1\n",
    "            if arr[left]<arr[left+1]:\n",
    "                while right+1<n and arr[right]<arr[right+1]:\n",
    "                    right += 1\n",
    "                if right<n-1 and arr[right]>arr[right+1]:\n",
    "                    while right+1<n and arr[right]>arr[right+1]:\n",
    "                        right += 1\n",
    "                    rs = max(rs,right-left+1)\n",
    "                else:\n",
    "                    right += 1\n",
    "            left = right\n",
    "        return rs\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #首先遍历 arr，寻找所有可能的山峰点。只有右侧的点小于当前点，即 arr[i + 1] < arr[i] ，才有可能是山峰。当找到山峰点，我们定义 l 和 r 分别向左向右寻找山脚，只有两个山脚不等于山峰时，即 l !== i && r !== i ，才计算山的长度，记入ans。\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        k=len(arr)\n",
    "        max_len=0\n",
    "        if(k<3):\n",
    "            return 0\n",
    "        for i in range(1,k-1):\n",
    "            l,r=i,i\n",
    "            #计算到中间值最高的\n",
    "            if(arr[i]>arr[i-1]) and (arr[i]>arr[i+1]):\n",
    "                while l-1>=0 and arr[l]>arr[l-1]:\n",
    "                    l-=1\n",
    "                while r+1<k and arr[r]>arr[r+1]:\n",
    "                    r+=1\n",
    "                max_len = max(max_len,r-l+1)\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        cnt = 1\n",
    "        ans = 0\n",
    "        down = False\n",
    "        for x, y in pairwise(arr):\n",
    "            if x < y:\n",
    "                if down:\n",
    "                    cnt = 1\n",
    "                    down = False\n",
    "                cnt += 1\n",
    "            elif down := x > y:\n",
    "                if cnt > 1:\n",
    "                    cnt += 1\n",
    "                    if cnt > ans:\n",
    "                        ans = cnt\n",
    "            else:\n",
    "                cnt = 1\n",
    "\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        # 遇到上升记录左侧\n",
    "        l, ans, up, down = 0, 0, False, False\n",
    "        for i in range(1, len(arr)):\n",
    "            # 升\n",
    "            if arr[i] > arr[i-1]:\n",
    "                if down: # 前面是降，重新定位升的开始位置\n",
    "                    l = i - 1\n",
    "                up = True\n",
    "                down = False\n",
    "            # 降\n",
    "            elif arr[i] < arr[i-1]:\n",
    "                down = True\n",
    "            else: # 相等的重置状态\n",
    "                l = i\n",
    "                down = False\n",
    "                up = False\n",
    "                continue\n",
    "            # 满足先升后降\n",
    "            if up and down:\n",
    "                ans = max(ans, i - l + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        cnt = 1\n",
    "        ans = 0\n",
    "        down = False\n",
    "        for x, y in pairwise(arr):\n",
    "            if x == y:\n",
    "                cnt = 1\n",
    "                down = False\n",
    "            elif y > x:\n",
    "                if down:\n",
    "                    cnt = 1\n",
    "                cnt += 1\n",
    "                down = False\n",
    "            else:\n",
    "                if cnt > 1:\n",
    "                    cnt += 1\n",
    "                    if cnt > ans:\n",
    "                        ans = cnt\n",
    "                down = True\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        state = 0\n",
    "        res = 0\n",
    "        cnt = 0\n",
    "        n = len(arr)\n",
    "        pre = cnt\n",
    "        i = 0\n",
    "        while i < n-1:\n",
    "            if state == 0:\n",
    "                if arr[i]<arr[i+1]:\n",
    "                    state = 1\n",
    "                    cnt += 1\n",
    "            elif state == 1:\n",
    "                if arr[i]<arr[i+1]:\n",
    "                    cnt += 1\n",
    "                elif arr[i] == arr[i+1]:\n",
    "                    cnt = 0\n",
    "                    state = 0\n",
    "                elif arr[i]> arr[i+1]:\n",
    "                    cnt += 1\n",
    "                    state = 2\n",
    "                    if i == n-2:\n",
    "                        res = max(res,cnt+1)\n",
    "            elif state == 2:\n",
    "                if arr[i] > arr[i+1]:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    state = 0\n",
    "                    res = max(res,cnt+1)\n",
    "                    cnt = 0\n",
    "                    continue\n",
    "                if i == n-2:\n",
    "                    res = max(res,cnt+1)\n",
    "            pre = cnt\n",
    "            i +=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        length = 0\n",
    "        i = 1\n",
    "        while i < len(arr)-1:\n",
    "            peak = arr[i]> arr[i-1] and arr[i] > arr[i + 1]\n",
    "            if not peak:\n",
    "                i += 1\n",
    "                continue\n",
    "            \n",
    "            leftIndex = i - 1\n",
    "            while leftIndex >= 1  and arr[leftIndex-1] < arr[leftIndex]:\n",
    "                leftIndex -= 1\n",
    "            rightIndex = i + 1\n",
    "            while rightIndex < len(arr)-1 and arr[rightIndex+1] < arr[rightIndex]:\n",
    "                rightIndex += 1\n",
    "            \n",
    "            current_len = rightIndex + 1 - leftIndex\n",
    "            if length < current_len:\n",
    "                length = current_len\n",
    "            \n",
    "\n",
    "            i = rightIndex + 1\n",
    "        \n",
    "        return length\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        res = 0\n",
    "        left = 0\n",
    "        while left + 2 < n:\n",
    "            right = left + 1\n",
    "            if arr[left] < arr[left + 1]:\n",
    "                while right + 1 < n and arr[right] < arr[right + 1]:\n",
    "                    right += 1\n",
    "                if right < n - 1 and arr[right] > arr[right + 1]:\n",
    "                    while right + 1 < n and arr[right] > arr[right + 1]:\n",
    "                        right += 1\n",
    "                    res = max(res, right - left + 1)\n",
    "                else:\n",
    "                    right += 1\n",
    "            left = right\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        if len(arr)<3:\n",
    "            return 0\n",
    "        max_len = 0\n",
    "        left = 0\n",
    "\n",
    "        while left<len(arr)-2:\n",
    "            if arr[left+1]<=arr[left]:\n",
    "                left+= 1\n",
    "            else:\n",
    "                mid = left +1\n",
    "                while (mid<len(arr)-1) and  (arr[mid+1]>arr[mid]):\n",
    "                    mid += 1\n",
    "\n",
    "                right = mid +1\n",
    "                if (mid!=len(arr)-1 ) and (arr[right]!=arr[mid]):\n",
    "\n",
    "                    while (right<len(arr)-1) and (arr[right+1]<arr[right]):\n",
    "                        right += 1\n",
    "\n",
    "                    # print(left, mid, right)\n",
    "                    max_len = max( right-left+1, max_len)\n",
    "\n",
    "                while (right<len(arr)-1) and (arr[right+1]==arr[right]):\n",
    "                    right += 1\n",
    "\n",
    "                # print(left, mid, right)\n",
    "                # print(arr[left:right+1])\n",
    "                left = right\n",
    "\n",
    "        return max_len\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        N = len(arr)\n",
    "        width = 0\n",
    "        i = 1 \n",
    "        while i < N-1:\n",
    "            L, R = i-1, i+1\n",
    "            if arr[L] < arr[i] and arr[i] > arr[R]:\n",
    "                while L > 0 and arr[L-1] < arr[L]:\n",
    "                    L-=1\n",
    "                while R < N-1 and arr[R] > arr[R+1]:\n",
    "                    R += 1\n",
    "                width = max(width, R-L+1)\n",
    "            \n",
    "            i = R \n",
    "        return width"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        up = 0\n",
    "        down = 0\n",
    "        fixed_up = 0\n",
    "        ans = 0\n",
    "        if len(arr) < 3:\n",
    "            return 0\n",
    "        for i in range(1, len(arr)):\n",
    "            #print(arr[i])\n",
    "            if arr[i] == arr[i - 1]:\n",
    "                up = 0\n",
    "                down = 0\n",
    "                fixed_up = 0\n",
    "            elif arr[i] > arr[i - 1]:\n",
    "                up += 1\n",
    "                down = 0\n",
    "            elif arr[i] < arr[i - 1]:\n",
    "                if up != 0:\n",
    "                    fixed_up = up\n",
    "                    up = 0\n",
    "                down += 1\n",
    "                if fixed_up != 0:\n",
    "                    if fixed_up + down + 1 > ans:\n",
    "                        #print(i)\n",
    "                        ans = fixed_up + down + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        cnt = 1\n",
    "        ans = 0\n",
    "        down = False\n",
    "        for x, y in pairwise(arr):\n",
    "            if x < y:\n",
    "                if down:\n",
    "                    down = False\n",
    "                    cnt = 1\n",
    "                cnt += 1\n",
    "            elif down := x > y:\n",
    "                if cnt > 1:\n",
    "                    cnt += 1\n",
    "                    if cnt > ans:\n",
    "                        ans = cnt\n",
    "            else:\n",
    "                cnt = 1\n",
    "        return ans  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "      if not arr: return -1\n",
    "      \n",
    "      res, left, length = 0, 0, len(arr)\n",
    "      while left < length - 2:\n",
    "        right = left + 1\n",
    "        if arr[left] < arr[left + 1]:\n",
    "          while right < length - 1 and arr[right] < arr[right + 1]: right += 1\n",
    "          if right < length - 1 and arr[right] > arr[right + 1]:\n",
    "            while (right < length - 1 and arr[right] > arr[right + 1]): right += 1\n",
    "            res = max(res, right - left + 1)\n",
    "          else: right += 1\n",
    "        left = right\n",
    "      return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        left = 0\n",
    "        peek = 0\n",
    "        right = 0\n",
    "        i = 1\n",
    "        res = 0\n",
    "        while i < len(arr):\n",
    "            if arr[i] == arr[i-1]:\n",
    "                left = 0\n",
    "                right = 0\n",
    "                peek = i\n",
    "\n",
    "            if left == 0 and right == 0:\n",
    "                if arr[i] > arr[i-1]:\n",
    "                    peek = i\n",
    "                    left = 1\n",
    "                else:\n",
    "                    right = 1\n",
    "            elif left == 0:\n",
    "                if arr[i] > arr[i-1]:\n",
    "                    peek = i\n",
    "                    left = 1\n",
    "                    right = 0\n",
    "                else:\n",
    "                    right += 1\n",
    "            elif right == 0:\n",
    "                if arr[i] > arr[i-1]:\n",
    "                    left += 1\n",
    "                    peek = i \n",
    "                else:\n",
    "                    right = 1\n",
    "            else:\n",
    "                if arr[i] > arr[i-1]:\n",
    "                    left = 1\n",
    "                    peek = i\n",
    "                    right = 0\n",
    "                else:\n",
    "                    right += 1\n",
    "            if left > 0 and right > 0 and res < left + right +1:\n",
    "                res = left + right +1\n",
    "            # print(i, left, peek, right)\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        longmountain = 0\n",
    "        isup = False\n",
    "        isdown = False\n",
    "        tmp = 0\n",
    "        n = len(arr)\n",
    "        for i in range(n-1):\n",
    "            if (not isup) and (not isdown):\n",
    "                if arr[i+1]>arr[i]:\n",
    "                    isup = True\n",
    "                    isdown = False\n",
    "                    tmp = 2\n",
    "            elif (isup) and (not isdown):\n",
    "                if arr[i+1]>arr[i]:\n",
    "                    tmp +=1\n",
    "                elif arr[i+1]<arr[i]:\n",
    "                    isup = False\n",
    "                    isdown = True\n",
    "                    tmp +=1\n",
    "                    longmountain = max(longmountain, tmp)\n",
    "                else:\n",
    "                    isup = False\n",
    "                    isdown = False\n",
    "                    tmp = 0\n",
    "            elif (not isup) and (isdown):\n",
    "                if arr[i+1]<arr[i]:\n",
    "                    tmp +=1\n",
    "                    longmountain = max(longmountain, tmp)\n",
    "                elif arr[i+1]>arr[i]:\n",
    "                    longmountain = max(longmountain, tmp)\n",
    "                    isup = True\n",
    "                    isdown = False\n",
    "                    tmp = 2\n",
    "                else:\n",
    "                    longmountain = max(longmountain, tmp)\n",
    "                    isup = False\n",
    "                    isdown = False\n",
    "                    tmp = 0\n",
    "\n",
    "\n",
    "        return longmountain\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1, len(arr) - 1):\n",
    "            if arr[i - 1] < arr[i] and arr[i] > arr[i + 1]:\n",
    "                left = i - 1\n",
    "                right = i + 1\n",
    "                while left > 0 and arr[left - 1] < arr[left]:\n",
    "                    left -= 1\n",
    "                while right < len(arr) - 1 and arr[right + 1] < arr[right]:\n",
    "                    right += 1\n",
    "                ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        res = 0\n",
    "        # 山脉数组需要大于3\n",
    "        if len(arr) < 3:\n",
    "            return 0\n",
    "\n",
    "        # 固定山峰\n",
    "        for i in range(1, len(arr)-1):\n",
    "            \n",
    "            # 先寻找到山峰，然后分别向左右移动\n",
    "            # 只有当前点为山峰的情况，才在左右寻找最长山峰\n",
    "            if arr[i - 1] < arr[i] and arr[i + 1] < arr[i]:\n",
    "                left = i - 1\n",
    "                right = i + 1\n",
    "                # 向左移动\n",
    "                # 左半边山脉的长度\n",
    "                while left >= 0 and arr[left] < arr[left + 1]:\n",
    "                    left -= 1\n",
    "                # 向右移动\n",
    "                # 右半边山脉的长度\n",
    "                while right <= len(arr) - 1 and arr[right] < arr[right - 1]:\n",
    "                    right += 1\n",
    "\n",
    "                # 如果这个山脉比最长的山脉长，更新res\n",
    "                if right - left - 1 > res:\n",
    "                    res = right - left - 1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        if len(arr) < 3:\n",
    "            return 0\n",
    "        max_len = 0\n",
    "        res = []\n",
    "        for i in range(len(arr)):\n",
    "            if i != 0  and i + 1 != len(arr) and arr[i-1] < arr[i] and arr[i] > arr[i+1]:\n",
    "                # 算作一个山顶\n",
    "                if res:\n",
    "                    res.append(i)\n",
    "            elif (i == 0 and arr[i] < arr[i+1]) or (i +1 == len(arr) and arr[i] < arr[i-1]) or (i!=0 and i+1!= len(arr) and arr[i] <= arr[i-1] and arr[i] <= arr[i+1]):\n",
    "                # 算作一个山谷\n",
    "                if len(res) == 2:\n",
    "                    max_len = max(max_len, i - res[0] + 1)\n",
    "                res = [i]\n",
    "            \n",
    "        return max_len\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        #copy\n",
    "        lst = [0]\n",
    "        for a1,a2 in pairwise(arr):\n",
    "            if a1<a2:\n",
    "                if lst[-1]>0:\n",
    "                    lst[-1] += 1\n",
    "                else:\n",
    "                    lst.append(1)\n",
    "            elif a1>a2:\n",
    "                if lst[-1]<0:\n",
    "                    lst[-1]+=-1\n",
    "                else:\n",
    "                    lst.append(-1)\n",
    "            else:\n",
    "                if lst[-1]:\n",
    "                    lst.append(0)\n",
    "        return max((x-y+1 for x,y in pairwise(lst)if x>0 and y <0) ,default = 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr):\n",
    "        res = 0\n",
    "        left = right = 0\n",
    "        while right < len(arr) - 1:\n",
    "            up = down = trans = 0\n",
    "            while right < len(arr) - 1 and arr[right] < arr[right + 1]:\n",
    "                up = 1\n",
    "                right += 1\n",
    "            while right < len(arr) - 1 and arr[right] == arr[right + 1]:\n",
    "                right += 1\n",
    "                trans = 1\n",
    "            while right < len(arr) - 1 and arr[right] > arr[right + 1]:\n",
    "                down = 1\n",
    "                right += 1\n",
    "            if up + down == 2 and trans == 0:\n",
    "                res = max(res, right - left + 1)\n",
    "            left = right\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        fast=1\n",
    "        slow=0\n",
    "        n=len(arr)\n",
    "        if n<3:\n",
    "            return 0\n",
    "        flag=-1\n",
    "        flag1=-1\n",
    "        ans=-inf\n",
    "        while slow<n:\n",
    "            if flag1==-1 and fast<n and arr[fast]>arr[fast-1]:\n",
    "                fast+=1\n",
    "                flag=1\n",
    "                continue\n",
    "            \n",
    "            if flag==1 and fast<n and arr[fast]<arr[fast-1]:\n",
    "                fast+=1\n",
    "                flag1=1\n",
    "                # print(fast)\n",
    "                continue\n",
    "            # print(\"-----\",fast)\n",
    "            if flag1==1:\n",
    "                # print(fast,slow)\n",
    "                ans=max(ans,fast-slow)\n",
    "            slow+=1\n",
    "            fast=slow+1\n",
    "            flag=-1\n",
    "            flag1=-1\n",
    "        return ans if ans!=-inf else 0\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestMountain(self, arr: List[int]) -> int:\r\n",
    "        n = len(arr)\r\n",
    "        if n == 1:\r\n",
    "            return 0\r\n",
    "        maxlen, curlen, up = 0, 0, 1\r\n",
    "        for i in range(1, n):\r\n",
    "            if arr[i] > arr[i-1]:\r\n",
    "                if up:\r\n",
    "                    curlen += 1\r\n",
    "                else:\r\n",
    "                    up = 1\r\n",
    "                    maxlen = max(maxlen, curlen)\r\n",
    "                    curlen = 1\r\n",
    "            elif arr[i] < arr[i-1]:\r\n",
    "                if curlen > 0:\r\n",
    "                    curlen += 1\r\n",
    "                up = 0\r\n",
    "            else:\r\n",
    "                if not up:\r\n",
    "                    maxlen = max(maxlen, curlen)\r\n",
    "                curlen = 0\r\n",
    "        if not up:\r\n",
    "            maxlen = max(maxlen, curlen)\r\n",
    "        return maxlen if maxlen == 0 else maxlen + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        res = 0\n",
    "        for i in range(1, n - 1):\n",
    "            if arr[i] > arr[i + 1] and arr[i] > arr[i - 1]:\n",
    "                left = i - 1\n",
    "                right = i + 1\n",
    "                while left > 0 and arr[left - 1] < arr[left]:\n",
    "                    left -= 1\n",
    "                while right < n - 1 and arr[right + 1] < arr[right]:\n",
    "                    right += 1\n",
    "                if right - left + 1 > res:\n",
    "                    res = right - left + 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\r\n",
    "# @lc app=leetcode.cn id=845 lang=python3\r\n",
    "#\r\n",
    "# [845] 数组中的最长山脉\r\n",
    "#\r\n",
    "from typing import List\r\n",
    "# @lc code=start\r\n",
    "class Solution:\r\n",
    "    def longestMountain(self, arr: List[int]) -> int:\r\n",
    "        asc=0\r\n",
    "        dec=1\r\n",
    "        ret=0\r\n",
    "        dir=1\r\n",
    "        for i in range(1,len(arr)):\r\n",
    "            if arr[i]>arr[i-1]:\r\n",
    "                if dir<=0:\r\n",
    "                    asc=1\r\n",
    "                    dec=1\r\n",
    "                else:\r\n",
    "                    asc+=1\r\n",
    "                dir=1\r\n",
    "            elif arr[i]==arr[i-1]:\r\n",
    "                asc=0\r\n",
    "                dec=1\r\n",
    "                dir=0\r\n",
    "            else:\r\n",
    "                dir=-1\r\n",
    "                dec+=1\r\n",
    "                if asc>0:\r\n",
    "                    ret=max(ret,asc+dec)\r\n",
    "        return ret\r\n",
    "\r\n",
    "\r\n",
    "assert Solution().longestMountain([3,3,1])==0\r\n",
    "assert Solution().longestMountain([0,1,2,3,4,5,4,3,2,1,0])==11\r\n",
    "assert Solution().longestMountain([2,1,4,7,3,2,5])==5\r\n",
    "assert Solution().longestMountain([2,2,2])==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        N = len(arr)\n",
    "        width = 0\n",
    "\n",
    "        i = 1\n",
    "        while i < N-1:\n",
    "            L, R = i-1, i+1\n",
    "            if arr[i] >arr[L] and arr[i] >arr[R]:\n",
    "                while L> 0 and arr[L-1] < arr[L]:\n",
    "                    L -= 1\n",
    "                while R< N-1 and arr[R+1] < arr[R]:\n",
    "                    R += 1\n",
    "                width = max(width, R-L+1)\n",
    "            i = R\n",
    "        return width "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        fast=1\n",
    "        slow=0\n",
    "        n=len(arr)\n",
    "        if n<3:\n",
    "            return 0\n",
    "        flag=-1\n",
    "        flag1=-1\n",
    "        ans=-inf\n",
    "        while slow<n:\n",
    "            if flag1==-1 and fast<n and arr[fast]>arr[fast-1]:\n",
    "                fast+=1\n",
    "                flag=1\n",
    "                continue\n",
    "            \n",
    "            if flag==1 and fast<n and arr[fast]<arr[fast-1]:\n",
    "                fast+=1\n",
    "                flag1=1\n",
    "                # print(fast)\n",
    "                continue\n",
    "            # print(\"-----\",fast)\n",
    "            if flag1==1:\n",
    "                # print(fast,slow)\n",
    "                ans=max(ans,fast-slow)\n",
    "            slow+=1\n",
    "            fast=slow+1\n",
    "            flag=-1\n",
    "            flag1=-1\n",
    "        return ans if ans!=-inf else 0\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ans, l = 0, 0\n",
    "        while l + 2 < n:\n",
    "            r = l + 1\n",
    "            if arr[l] < arr[l + 1]:\n",
    "                while r + 1 < n and arr[r] < arr[r + 1]:\n",
    "                    r += 1\n",
    "                if r < n - 1 and arr[r] > arr[r + 1]:\n",
    "                    while r + 1 < n and arr[r] > arr[r + 1]:\n",
    "                        r += 1\n",
    "                    ans = max(ans, r - l + 1)\n",
    "            l = r\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestMountain(self, arr) -> int:\r\n",
    "        l = 0\r\n",
    "        r = 1\r\n",
    "        maxlen = 0\r\n",
    "        temp = 0\r\n",
    "        rise = True\r\n",
    "\r\n",
    "        for r in range(1, len(arr)):\r\n",
    "            temp = arr[r - 1]\r\n",
    "            if rise and temp < arr[r]:\r\n",
    "                continue\r\n",
    "            elif rise and temp == arr[r]:\r\n",
    "                l = r\r\n",
    "            elif rise and temp > arr[r]:\r\n",
    "                if r - l > 1:\r\n",
    "                    if r == len(arr) - 1 or arr[r+1] >= arr[r]:\r\n",
    "                        maxlen = max(maxlen, r - l + 1)\r\n",
    "                        l = r\r\n",
    "                    rise = False\r\n",
    "                else:\r\n",
    "                    l = r\r\n",
    "            elif not rise and temp > arr[r]:\r\n",
    "\r\n",
    "                if r == len(arr) - 1:\r\n",
    "                    maxlen = max(maxlen, r - l + 1)\r\n",
    "                continue\r\n",
    "            elif not rise and temp == arr[r]:\r\n",
    "                rise = True\r\n",
    "                maxlen = max(maxlen, r - 1 - l)\r\n",
    "                l = r\r\n",
    "            elif not rise and temp < arr[r]:\r\n",
    "                rise = True\r\n",
    "                maxlen = max(maxlen, r - l)\r\n",
    "                l = r - 1\r\n",
    "\r\n",
    "        return maxlen\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        N = len(arr)\n",
    "        width = 0\n",
    "\n",
    "        i = 1\n",
    "        while i < N-1:\n",
    "            L, R = i, i\n",
    "            while L>=1 and arr[L-1] < arr[L]:\n",
    "                L -= 1\n",
    "            while R<= N-2 and arr[R+1] < arr[R]:\n",
    "                R += 1\n",
    "\n",
    "            if L< i and R > i : width = max(width, R-L+1)\n",
    "            i+= 1\n",
    "        return width "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        N = len(arr)\n",
    "        width = 0\n",
    "\n",
    "        i = 1\n",
    "        while i < N-1:\n",
    "            L, R = i-1, i+1\n",
    "            if arr[i] >arr[L] and arr[i] >arr[R]:\n",
    "                while L> 0 and arr[L-1] < arr[L]:\n",
    "                    L -= 1\n",
    "                while R< N-1 and arr[R+1] < arr[R]:\n",
    "                    R += 1\n",
    "                width = max(width, R-L+1)\n",
    "            i = R\n",
    "        return width "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        # 双指针, 暴力算法\n",
    "        res = 0\n",
    "        for i in range(1, len(arr)-1):\n",
    "            if arr[i-1]<arr[i] and arr[i+1]<arr[i]:\n",
    "                left, right = i-1, i+1\n",
    "                while left>0 and arr[left-1]<arr[left]: left -= 1\n",
    "                while right<len(arr)-1 and arr[right+1]<arr[right]: right += 1\n",
    "                if right-left+1 > res: res = right-left+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        ans = 0\n",
    "        i = 1\n",
    "        n = len(arr)\n",
    "        mode = -1\n",
    "        head = 0\n",
    "        while i<n:\n",
    "            if arr[i]==arr[i-1]:\n",
    "                if mode == 1:\n",
    "                    ans = max(ans, i-head)\n",
    "                head = i\n",
    "                mode = -1\n",
    "            elif arr[i]>arr[i-1]:\n",
    "                if mode==1:\n",
    "                    ans = max(ans, i-head)\n",
    "                    head = i-1\n",
    "                elif mode == -1:\n",
    "                    head = i-1\n",
    "                mode = 0 \n",
    "            else:\n",
    "                if mode==-1:\n",
    "                    head = i-1\n",
    "                elif mode==0:\n",
    "                    mode=1\n",
    "            i+=1\n",
    "        if mode ==1:\n",
    "            ans = max(ans, i-head)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        N = len(arr)\n",
    "        width = 0\n",
    "\n",
    "        i = 1\n",
    "        while i < N-1:\n",
    "            if arr[i] >arr[i-1] and arr[i] >arr[i+1]:\n",
    "                L, R = i, i\n",
    "                while L>=1 and arr[L-1] < arr[L]:\n",
    "                    L -= 1\n",
    "                while R<= N-2 and arr[R+1] < arr[R]:\n",
    "                    R += 1\n",
    "                width = max(width, R-L+1)\n",
    "            i+= 1\n",
    "        return width "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        left=[0]*n\n",
    "        right=[0]*n\n",
    "        for i in range(1,n):\n",
    "            if arr[i]>arr[i-1]:\n",
    "                left[i]=left[i-1]+1\n",
    "        for i in range(-2,-n-1,-1):\n",
    "            if arr[i]>arr[i+1]:\n",
    "                right[i]=right[i+1]+1\n",
    "        a=0\n",
    "        for i in range(n):\n",
    "            if left[i]>0 and right[i]>0:\n",
    "                a=max(a,left[i]+ right[i]+1)\n",
    "        return a\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        up = [1] * n\n",
    "        down = [1] * n\n",
    "        # 求前后最长子序列\n",
    "        for i in range(1, n):\n",
    "            if arr[i] > arr[i - 1]:\n",
    "                up[i] = up[i - 1] + 1\n",
    "        for i in range(n - 2, 0, -1):\n",
    "            if arr[i] > arr[i + 1]:\n",
    "                down[i] = down[i + 1] + 1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if up[i] > 1 and down[i] > 1:\n",
    "                ans = max(ans, up[i] + down[i] - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        left, right = 0, 0\n",
    "        res = 0\n",
    "        reslist = list()\n",
    "        flag = 0\n",
    "        indexleft = -1\n",
    "        indexright = -1\n",
    "        for i in range(0, len(arr) - 1):\n",
    "            #print(\"arr[\" + str(i) + \"]\" + \"=\" + str(arr[i]))\n",
    "            if arr[i] < arr[i + 1] and flag == 0:\n",
    "                #print(\"11111\")\n",
    "                flag = 1\n",
    "                left = i\n",
    "            elif arr[i] > arr[i + 1] and flag == 1:\n",
    "                #print(\"22222\")\n",
    "                flag = -1\n",
    "            elif arr[i] < arr[i + 1] and flag == -1:\n",
    "                #print(\"33333\")\n",
    "                right = i\n",
    "                if right - left > res:\n",
    "                    indexright = right\n",
    "                    indexleft = left\n",
    "                res = max(res, right - left)\n",
    "                flag = 1\n",
    "                left = i\n",
    "            elif arr[i] == arr[i + 1]:\n",
    "                if flag == -1:\n",
    "                    right = i\n",
    "                    if right - left > res:\n",
    "                        indexright = right\n",
    "                        indexleft = left\n",
    "                    res = max(res, right - left)\n",
    "                flag = 0\n",
    "        if flag == -1:\n",
    "            right = len(arr) - 1\n",
    "            if right - left > res:\n",
    "                indexright = right\n",
    "                indexleft = left\n",
    "            res = max(res, right - left)\n",
    "        #print(res)\n",
    "        if indexleft != -1 and indexright != -1:\n",
    "            for i in range(indexleft, indexright + 1):\n",
    "                reslist.append(arr[i])\n",
    "        #print(reslist)\n",
    "        return len(reslist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        if len(arr) < 3:\n",
    "            return 0\n",
    "        max_len = 0\n",
    "        res = []\n",
    "        for i in range(len(arr)):\n",
    "            if i != 0  and i + 1 != len(arr) and arr[i-1] < arr[i] and arr[i] > arr[i+1]:\n",
    "                # 算作一个山顶\n",
    "                if res:\n",
    "                    res.append(i)\n",
    "            elif (i == 0 and arr[i] < arr[i+1]) or (i +1 == len(arr) and arr[i] < arr[i-1]) or (i!=0 and i+1!= len(arr) and arr[i] <= arr[i-1] and arr[i] <= arr[i+1]):\n",
    "                # 算作一个山谷\n",
    "                if len(res) == 2:\n",
    "                    print(res, i)\n",
    "                    max_len = max(max_len, i - res[0] + 1)\n",
    "                res = [i]\n",
    "            \n",
    "        return max_len\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ary = [0]*n\n",
    "        ary2 = [0]*n\n",
    "        for i in range(1,n-1):\n",
    "            if arr[i-1]<arr[i]:\n",
    "                ary[i] = ary[i-1]+1\n",
    "            else:\n",
    "                ary[i] = 0\n",
    "        for i in range(n-2,0,-1):\n",
    "            if arr[i+1]<arr[i]:\n",
    "                ary2[i] = ary2[i+1]+1\n",
    "            else:\n",
    "                ary2[i] = 0\n",
    "        ans = 0\n",
    "        for i in range(1,n-1):\n",
    "            if ary[i] and ary2[i]:\n",
    "                ans = max(ans,ary[i]+ary2[i]+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestMountain(self, arr: List[int]) -> int:\r\n",
    "        res = 0\r\n",
    "        lis = [0, 0]\r\n",
    "        for i in range(1, len(arr)):\r\n",
    "            if arr[i] - arr[i - 1] > 0:\r\n",
    "                if lis[1] == 0:\r\n",
    "                    lis[0] += 1\r\n",
    "                else:\r\n",
    "                    lis = [1, 0]\r\n",
    "            elif arr[i] - arr[i - 1] < 0:\r\n",
    "                if lis[0] == 0:\r\n",
    "                    lis = [0, 0]\r\n",
    "                else:\r\n",
    "                    lis[1] += 1\r\n",
    "                    res = max(res, sum(lis) + 1)\r\n",
    "            else:\r\n",
    "                lis = [0, 0]\r\n",
    "        return(res) \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "      if not arr: return -1\n",
    "      \n",
    "      length = len(arr)\n",
    "      left = res = 0\n",
    "      while left + 2 < length:\n",
    "        right = left + 1\n",
    "        if arr[left] < arr[left + 1]:\n",
    "          while right < length - 1 and arr[right] < arr[right + 1]:\n",
    "            right += 1\n",
    "          if (right < length - 1 and arr[right] > arr[right + 1]):\n",
    "            while right < length - 1 and arr[right] > arr[right + 1]:\n",
    "              right += 1\n",
    "            res = max(res, right - left + 1)\n",
    "          else: \n",
    "            right += 1\n",
    "        left = right\n",
    "      return res\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        arr_length = len(arr)\n",
    "        left_slope_length_list = [0] * arr_length\n",
    "        right_slope_length_list = [0] * arr_length\n",
    "        answer = 0\n",
    "        for index in range(1, arr_length):\n",
    "            if arr[index] > arr[index - 1]:\n",
    "                left_slope_length_list[index] = left_slope_length_list[index - 1] + 1\n",
    "        for index in range(arr_length - 2, -1, -1):\n",
    "            if arr[index] > arr[index + 1]:\n",
    "                right_slope_length_list[index] = right_slope_length_list[index + 1] + 1\n",
    "        for index in range(1, arr_length - 1):\n",
    "            if left_slope_length_list[index] and right_slope_length_list[index]:\n",
    "                answer = max(answer, left_slope_length_list[index] + right_slope_length_list[index] + 1)\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        up = [0 for _ in range(len(arr))]\n",
    "        down = [0 for _ in range(len(arr))]\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i] > arr[i-1]:\n",
    "                up[i] += up[i-1] + 1\n",
    "        for i in range(len(arr)-2, -1, -1):\n",
    "            if arr[i] > arr[i+1]:\n",
    "                down[i] += down[i+1] + 1\n",
    "        ans = 0\n",
    "        for i in range(len(arr)):\n",
    "            if up[i] > 0 and down[i] > 0:\n",
    "                ans = max(ans, up[i] + down[i] + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        # left[i]: number of elements that are smaller than arr[i]\n",
    "        left, right = [0]*n, [0]*n\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if arr[i]>arr[i-1]:\n",
    "                left[i]=left[i-1]+1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if arr[i]>arr[i+1]:\n",
    "                right[i]=right[i+1]+1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if left[i]*right[i] != 0:\n",
    "                ans = max(ans, left[i]+right[i]+1)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        up = [1]*n\n",
    "        down = [1]*n\n",
    "        for i in range(1, n):\n",
    "            if arr[i] > arr[i - 1]:\n",
    "                up[i] = up[i - 1] + 1\n",
    "            if arr[n - i - 1] > arr[n - i]:\n",
    "                down[n - i - 1] = down[n - i] + 1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if up[i] > 1 and down[i] > 1:\n",
    "                ans = max(ans, up[i] + down[i] - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        left_max = [0] * n\n",
    "        right_max = [0] * n\n",
    "        for i in range(1,n):\n",
    "            if arr[i]>arr[i-1]:\n",
    "                left_max[i]=left_max[i-1]+1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if arr[i]>arr[i+1]:\n",
    "                right_max[i]=right_max[i+1]+1\n",
    "\n",
    "        max_res = [0] * n\n",
    "        for i in range(n):\n",
    "            if left_max[i]>0 and right_max[i]>0:\n",
    "                max_res[i] = left_max[i]+1+right_max[i]\n",
    "\n",
    "        #print(left_max)\n",
    "        #print(right_max)\n",
    "        #print(max_res)\n",
    "        return max(max_res)\n",
    "          \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        l, r = [0]*n, [0]*n\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if arr[i]>arr[i-1]:\n",
    "                l[i] = l[i-1]+1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if arr[i]>arr[i+1]:\n",
    "                r[i] = r[i+1]+1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(1, n-1):\n",
    "            if l[i] > 0 and r[i] > 0:\n",
    "                ans = max(ans, l[i]+r[i]+1)\n",
    "        return ans\n",
    "\n",
    "\n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestMountain(self, arr) -> int:\r\n",
    "        l = 0\r\n",
    "        r = 1\r\n",
    "        maxlen = 0\r\n",
    "        temp = 0\r\n",
    "        rise = True\r\n",
    "\r\n",
    "        for r in range(1, len(arr)):\r\n",
    "            temp = arr[r - 1]\r\n",
    "            if rise and temp < arr[r]:\r\n",
    "                print(111)\r\n",
    "                continue\r\n",
    "            elif rise and temp == arr[r]:\r\n",
    "                print(222)\r\n",
    "                l = r\r\n",
    "            elif rise and temp > arr[r]:\r\n",
    "                print(333, l, r)\r\n",
    "                if r - l > 1:\r\n",
    "                    if r == len(arr) - 1 or arr[r+1] >= arr[r]:\r\n",
    "                        maxlen = max(maxlen, r - l + 1)\r\n",
    "                        l = r\r\n",
    "                    rise = False\r\n",
    "                else:\r\n",
    "                    l = r\r\n",
    "            elif not rise and temp > arr[r]:\r\n",
    "                print(444)\r\n",
    "                if r == len(arr) - 1:\r\n",
    "                    maxlen = max(maxlen, r - l + 1)\r\n",
    "                continue\r\n",
    "            elif not rise and temp == arr[r]:\r\n",
    "                print(555)\r\n",
    "                rise = True\r\n",
    "                maxlen = max(maxlen, r - 1 - l)\r\n",
    "                l = r\r\n",
    "            elif not rise and temp < arr[r]:\r\n",
    "                print(666)\r\n",
    "                rise = True\r\n",
    "                maxlen = max(maxlen, r - l)\r\n",
    "                l = r - 1\r\n",
    "\r\n",
    "        return maxlen\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left = [1 for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            left[i] = left[i-1] + 1 if arr[i] > arr[i-1] else 1\n",
    "        right = [1 for _ in range(n)]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            right[i] = right[i+1] + 1 if arr[i] > arr[i+1] else 1\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if left[i] > 1 and right[i] > 1:\n",
    "                res = max(left[i]+right[i]-1, res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        if not arr:\n",
    "            return 0\n",
    "        \n",
    "        n = len(arr)\n",
    "\n",
    "        left = [0] * n\n",
    "        for i in range(1, n):\n",
    "            left[i] = (left[i-1] + 1 if arr[i - 1] < arr[i] else 0)\n",
    "\n",
    "        right = [0] * n\n",
    "        for i in range(n-2, -1, -1):\n",
    "            right[i] = (right[i+1] + 1 if arr[i+1] < arr[i] else 0)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if left[i] > 0 and right[i] > 0:\n",
    "                ans = max(ans, left[i] + right[i] + 1)\n",
    "            \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        if not arr:\n",
    "            return 0\n",
    "            \n",
    "        n = len(arr)\n",
    "        left = [0] * n\n",
    "        for i in range(1, n):\n",
    "            left[i] = (left[i - 1] + 1 if arr[i - 1] < arr[i] else 0)\n",
    "        \n",
    "        right = [0] * n\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            right[i] = (right[i + 1] + 1 if arr[i + 1] < arr[i] else 0)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if left[i] > 0 and right[i] > 0:\n",
    "                ans = max(ans, left[i] + right[i] + 1)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 类似于接雨水\n",
    "# 山顶为局部最大，local maximum 的定义是\n",
    "# left < x > right for any x\n",
    "# 山脉的长度，首先需要找到局部最大，再从左从右\n",
    "# 延伸。这样就是两层循环，第一层循环从左到右遍历\n",
    "# 整个数组，第二层循环以数组内每一个数为中心，向左向右延伸。\n",
    "# 然而，对于数组内的每一个点，如果它左侧比他小的数大于等于 1，\n",
    "# 右侧比他大的数大于等于 1，那么这个数就可以作为山顶\n",
    "# 因此我们可以通过动态规划的方法储存每一个点，左边比他小的数量\n",
    "# 和右边比他小的数量，那么最后的总长度就为左边小的数量 + 右边小的数量 + 1\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        if n < 3: return 0\n",
    "\n",
    "        left = [0] * n\n",
    "        for i in range(1, n):\n",
    "            left[i] = left[i - 1] + 1 if arr[i - 1] < arr[i] else 0\n",
    "\n",
    "        right = [0] * n\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            right[i] = right[i + 1] + 1 if arr[i + 1] < arr[i] else 0\n",
    "\n",
    "        len_mountain = 0\n",
    "        for i in range(n):\n",
    "            if left[i] and right[i]:\n",
    "                len_mountain = max(len_mountain, left[i] + right[i] + 1)\n",
    "\n",
    "        return len_mountain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        left_arr=[0 for i in range(n)]\n",
    "        right_arr=[0 for i in range(n)]\n",
    "        for i in range(n):\n",
    "            if i>0 and arr[i]>arr[i-1]:\n",
    "                left_arr[i]=left_arr[i-1]+1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if i<n-1 and arr[i]>arr[i+1]:\n",
    "                right_arr[i]=right_arr[i+1]+1\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            if left_arr[i]!=0 and right_arr[i]!=0:\n",
    "                ans=max(ans, left_arr[i]+right_arr[i]+1)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        if not arr:\n",
    "            return 0\n",
    "            \n",
    "        n = len(arr)\n",
    "        left = [0] * n\n",
    "        for i in range(1, n):\n",
    "            left[i] = (left[i - 1] + 1 if arr[i - 1] < arr[i] else 0)\n",
    "        \n",
    "        right = [0] * n\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            right[i] = (right[i + 1] + 1 if arr[i + 1] < arr[i] else 0)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if left[i] > 0 and right[i] > 0:\n",
    "                ans = max(ans, left[i] + right[i] + 1)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        # precompute how long we can expand towards left/right from i\n",
    "        left = [0 for _ in range(n)]\n",
    "        upstreak = 0\n",
    "        for i in range(n):\n",
    "            if i > 0 and arr[i] > arr[i-1]:\n",
    "                upstreak += 1\n",
    "            else:\n",
    "                upstreak = 0\n",
    "            left[i] = upstreak\n",
    "        right = [0 for _ in range(n)]\n",
    "        downstreak = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if i < n - 1 and arr[i] > arr[i+1]:\n",
    "                downstreak += 1\n",
    "            else:\n",
    "                downstreak = 0\n",
    "            right[i] = downstreak\n",
    "        print(left, right)\n",
    "        # enumerate peaks\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            # when it can be a peak\n",
    "            if left[i] > 0 and right[i] > 0:\n",
    "                res = max(res, left[i] + right[i] + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestMountain(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left, right = [0] * n, [0] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            if not stack or arr[i] > stack[-1]:\n",
    "                left[i] = len(stack)\n",
    "                stack.append(arr[i])\n",
    "            else:\n",
    "                stack.clear()\n",
    "                stack.append(arr[i])\n",
    "                left[i] = 0\n",
    "        \n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if not stack or arr[i] > stack[-1]:\n",
    "                right[i] = len(stack)\n",
    "                stack.append(arr[i])\n",
    "            else:\n",
    "                stack.clear()\n",
    "                stack.append(arr[i])\n",
    "                right[i] = 0\n",
    "        print(left, right)\n",
    "        ans = 0\n",
    "        for l, r in zip(left, right):\n",
    "            if l > 0 and r > 0:\n",
    "                ans = max(ans, l + r + 1)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
